package test.algorithm;

import cn.demoncat.util.lang.entity.data.LinkedGraph;
import org.junit.Test;

/**
 * 图 - 最小生成树
 * 
 * @author 延晓磊
 *
 * @since 2020年7月31日
 */
public class GraphMst {

	@Test
	public void test() {
		// 图
		LinkedGraph<String, String, Integer> graph = new LinkedGraph<>();
		graph.addVertex("A");
		graph.addVertex("B");
		graph.addVertex("C");
		graph.addVertex("D");
		graph.addVertex("E");
		graph.addVertex("F");
		graph.addVertex("G");
		graph.setEdge("A", "B", 12);
		graph.setEdge("A", "F", 16);
		graph.setEdge("A", "G", 14);
		graph.setEdge("B", "F", 7);
		graph.setEdge("B", "C", 10);
		graph.setEdge("C", "F", 6);
		graph.setEdge("C", "D", 3);
		graph.setEdge("D", "E", 4);
		graph.setEdge("C", "E", 5);
		graph.setEdge("E", "F", 2);
		graph.setEdge("E", "G", 8);
		graph.setEdge("G", "F", 9);
		// 最小生成树 - 普里姆算法：AB,BF,FE,ED,EC,EG
		System.out.println(graph.getMstByPrim());
		// 最小生成树 - 克鲁斯卡尔算法：EF,CD,DE,BF,EG,AB
		System.out.println(graph.getMstByKruskal());
	}

}
